package com.kevin.Code.LinkNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Vinlee Xiao
 * @Classname CopyListWithRandomPointer
 * @Description Leetcode 138. 复制带随机指针的链表 中等难度 题解思路很好
 * @Date 2021/10/25 20:09
 * @Version 1.0
 */
public class CopyListWithRandomPointer {
    /**
     * 用于存储心结点到老节点的映射
     */
    HashMap<RandomNode, RandomNode> cacheNode = new HashMap<>();

    /**
     * 做法较复杂不可行
     * 思路:目标找到序列到序列的映射
     *
     * @param head
     * @return
     */
    public RandomNode copyRandomList(RandomNode head) {

        RandomNode m1 = head;
        //哑节点
        RandomNode dummy = new RandomNode(-1);
        RandomNode m2 = dummy;
        //结点到链表真实顺序索引的映射
        HashMap<RandomNode, Integer> NodeToIndex = new HashMap<>();
        //顺序索引到结点的映射
        HashMap<Integer, RandomNode> indexToNode = new HashMap<>();
        //记录复制的链表序号到Node的映射
        HashMap<Integer, RandomNode> copyNode = new HashMap<>();

        int index = 0;
        //求出
        while (m1 != null) {
            RandomNode node = new RandomNode(m1.val);
            m2.next = node;
            m2 = m2.next;
            NodeToIndex.put(m1, index);
            //随意指针可能指向为空
            if (m1.random != null) {
                indexToNode.put(index, m1.random);
            }
            //记录新建的链表顺序和结点的对应顺序
            copyNode.put(index, node);
            index++;
        }

        RandomNode move = dummy.next;
        //index同时可以计算除链表的数据大小
        //遍历indexToNode
        for (int i = 0; i < index; i++) {
            if (indexToNode.containsKey(i)) {
                //先得到索引到结点的映射
                RandomNode NodeAddr = indexToNode.get(i);
                RandomNode node = copyNode.get(NodeToIndex.get(NodeAddr));
                move.random = node;
            }
            move = move.next;
        }


        return dummy.next;
    }

    /**
     * 方法二:
     * 递归解决：思路非常好
     * 官方题解：利用递归来解决完问题
     *
     * @param head
     * @return
     */
    public RandomNode copyRandomList1(RandomNode head) {

        if (!cacheNode.containsKey(head)) {

            RandomNode randomNode = new RandomNode(head.val);

            //放入HashMap中，
            cacheNode.put(head, randomNode);

            randomNode.next = copyRandomList1(head.next);
            randomNode.random = copyRandomList1(head.random);
        }

        return cacheNode.get(head);
    }

    /**
     * 方法三：参考其他人题解
     *
     * @param head
     * @return
     */
    public RandomNode copyRandomList2(RandomNode head) {

        HashMap<RandomNode, RandomNode> nodeToNewNode = new HashMap<>();
        //复制为头结点
        RandomNode moveHead = head;

        while (moveHead != null) {

            RandomNode newNode = new RandomNode(moveHead.val);
            nodeToNewNode.put(moveHead, newNode);
        }

        //重新对moveHead赋值
        moveHead = head;
        while (moveHead != null) {
            //新结点的下一个结点指向该节点的下一个结点
            nodeToNewNode.get(moveHead).next = nodeToNewNode.get(moveHead.next);
            //新结点的
            if (moveHead.random != null) {
                nodeToNewNode.get(moveHead).random = nodeToNewNode.get(moveHead.random);
            }
            moveHead = moveHead.next;
        }

        return nodeToNewNode.get(head);
    }

}

class RandomNode {
    int val;
    RandomNode next;
    RandomNode random;

    public RandomNode(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
